package test;

import comment.Comment;

/**
 *create by tbj
 */
public class MyQuick_two {
	private static int partition(int[] a,int l,int r){
		Comment.swapIntArr(a, l, (int)Math.random()*(r-l+1)+l);
		int v=a[l];
		int i=l+1;
		int j=r;
		while(true){
			while(i<=r && a[i]<v){
				i++;
			}
			while(j>=l+1 && a[j]>v){
				j--;
			}
			if(i > j){
				break;
			}
			Comment.swapIntArr(a, i, j);
		}
		Comment.swapIntArr(a, l, j);
		return j;
	}
	private static void _sort(int[] a,int l,int r){
		if(l >= r){
			return;
		}
		int p=partition(a,l,r);
		_sort(a, l, p-1);
		_sort(a, p+1, r);
	}
	public static void sort(int[] a){
		int n=a.length;
		_sort(a,0,n-1);
	}
	public static void main(String[] args) {
		int[] a=Comment.getSortIntArr();
		MyQuick_two.sort(a);
		for (int i : a) {
			System.out.print(i+" ");
		}
	}
}
